//@原文链接：https://blog.csdn.net/ITSOK_123/article/details/124324086
//库函数使用：
class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};
//暴力解法：
int strStr(string haystack, string needle) {
        int len1=haystack.size(),len2 = needle.size();
        //从前到后遍历haystack字符串进行判断
        for(int i=0;i+len2<=len1;i++){
            //标记本次位置i是否成功匹配
            bool flag = true;
            //基于当前位置i开始的len2个字符串和needle作比较
            for(int j=0;j<len2;j++){
                if(haystack[i+j]!=needle[j]){
                    flag = false;
                    break;
                }
            }
            //如果本次匹配成功则返回i，否则继续循环
            if(flag){
                    return i;
            }
        }
        //匹配失败
        return -1;
    }
//KMP算法匹配

class Solution {
public:
    void getNext(int *next,const string &s){
        //j用来记录之前
        int j=0;
        next[0]=0;
        for(int i=1;i<s.size();i++){
            //当前字符不匹配则寻找更小的最大相等前后缀长度
            //直到遇到和当前的字符i相等的第next[j-1]个字符
            while(j>0 && s[i]!=s[j]){
                j=next[j-1];
            }
            //当前字符匹配则最大相等前后缀长度增长1单位
            if(s[i]==s[j]){
                j++;
            }
            //更新当前位置前的最大相等前后缀长度
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0)    return 0;
        int len1 = haystack.size(),len2 = needle.size();
        int next[len2];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<len1;i++){
            //当前字符不匹配则根据数组回退
            while(j && haystack[i]!=needle[j]){
                j=next[j-1];
            }
            //相等则同时右移
            if(haystack[i]==needle[j]){
                j++;
            }
            //匹配完成退出
            if(j==len2) return i-len2+1;
        }
        return -1;
    }
};